package com.zhanghp.class018;

import com.zhanghp.common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <p>不用递归，用迭代的方式实现二叉树的三序遍历</p>
 * <p>stack 基于后进先出</p>
 * <ul>
 *     先序
 *     <li>
 *         打印根节点
 *     </li>
 *     <li>
 *         加入右节点（后进先出，所以先加入右节点）
 *     </li>
 *     <li>
 *         加入左节点
 *     </li>
 *     <li>
 *         循环上面2步骤，打印
 *     </li>
 * </ul>
 *
 * @author zhanghp
 * @since 2024/2/23 13:42
 */
public class BinaryTreeTraversalIteration {


    // 先序
    // stack LIFO 后进先出
    public static void preOrder(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            System.out.print(head.val + " ");
            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }
        System.out.println();
    }

    // 中序 左根右
    public static void inOrder(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.val + " ");
                head = head.right;
            }
        }


    }

    // 根据先序遍历，变成-》头右左 ，反过来：左右头（后序遍历）
    // 然后用另一个栈接收
    public static void posOrderTwoStacks(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<Integer> collect = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                // 接收
                collect.push(head.val);
                if (head.left != null) {
                    stack.push(head.left);
                }
                if (head.right != null) {
                    stack.push(head.right);
                }
            }
            while (!collect.isEmpty()) {
                System.out.print(collect.pop() + " ");
            }
        }

    }


    /**
     * <p>
     * 单个栈实现后序遍历
     * </p>
     * <p>
     * 原理：利用一个标记节点，来区分左右孩子是否遍历完，在进行打印头节点
     * </p>
     * <ol>
     *     <li>
     *         左节点处理：当前节点左孩子是否为空 & 当前节点左孩子和标记节点head是否不相等 & 当前节点右孩子和标记节点head是否不相等（这个条件判断右节点是否遍历完）
     *     </li>
     *     <li>
     *         右节点处理：当前节点的右孩子是否为空 & 当前节点的右孩子和标记节点head是否相等
     *     </li>
     *     <li>
     *         头节点处理：上述2个条件不成立，说明该执行头节点，当前节点pop，并标记节点存储为pop后的节点地址，用于当前节点的老爸来区分这3个逻辑
     *     </li>
     * </ol>
     *
     * @param head
     */
    public static void posOrderOneStack(TreeNode head) {
        if (head != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                TreeNode node = stack.peek();
                if (node.left != null && node.left != head && node.right != head) {
                    stack.push(node.left);
                } else if (node.right != null && node.right != head) {
                    stack.push(node.right);
                } else {
                    head = stack.pop();
                    System.out.print(head.val + " ");
                }
            }
        }
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);
        preOrder(head);
        System.out.println("先序遍历非递归版");
        inOrder(head);
        System.out.println("中序遍历非递归版");
        posOrderTwoStacks(head);
        System.out.println("后序遍历非递归版 - 2个栈实现");
        posOrderOneStack(head);
        System.out.println("后序遍历非递归版 - 1个栈实现");

    }

    // 用一个栈完成先序遍历
    // 测试链接 : https://leetcode.cn/problems/binary-tree-preorder-traversal/
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            ans.add(pop.val);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return ans;
    }

    // 用一个栈完成中序遍历
    // 测试链接 : https://leetcode.cn/problems/binary-tree-inorder-traversal/
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode pop = stack.pop();
                ans.add(pop.val);
                root = pop.right;
            }
        }
        return ans;
    }

    // 用两个栈完成后序遍历
    // 提交时函数名改为postorderTraversal
    // 测试链接 : https://leetcode.cn/problems/binary-tree-postorder-traversal/
    public static List<Integer> postorderTraversalTwoStacks(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> collect = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            collect.push(pop.val);

            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        while (!collect.isEmpty()) {
            ans.add(collect.pop());
        }
        return ans;
    }

    // 用一个栈完成后序遍历
    // 提交时函数名改为postorderTraversal
    // 测试链接 : https://leetcode.cn/problems/binary-tree-postorder-traversal/
    public static List<Integer> postorderTraversalOneStack(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            if (cur.left != null && cur.left != root &&cur.right != root) {
                stack.push(cur.left);
            }else if(cur.right != null && cur.right != root){
                stack.push(cur.right);
            }else {
                root = stack.pop();
                ans.add(cur.val);
            }
        }
        return ans;
    }


}
